{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Pond Sizes LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pondSizes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #水域大小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个用于表示一片土地的整数矩阵<code>land</code>，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。</p>\n",
    "<p><strong>示例：</strong></p>\n",
    "<pre><strong>输入：</strong>\n",
    "[\n",
    "  [0,2,1,0],\n",
    "  [0,1,0,1],\n",
    "  [1,1,0,1],\n",
    "  [0,1,0,1]\n",
    "]\n",
    "<strong>输出：</strong> [1,2,4]\n",
    "</pre>\n",
    "<p><strong>提示：</strong></p>\n",
    "<ul>\n",
    "<li><code>0 < len(land) <= 1000</code></li>\n",
    "<li><code>0 < len(land[i]) <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pond-sizes-lcci](https://leetcode.cn/problems/pond-sizes-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pond-sizes-lcci](https://leetcode.cn/problems/pond-sizes-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m=len(land)\n",
    "        n=len(land[0])\n",
    "\n",
    "        ans=[]\n",
    "        for i in range (0,m):\n",
    "            for j in range (0,n):\n",
    "                if land[i][j]==0:\n",
    "                    tem=0\n",
    "                    queue=[[i,j]]\n",
    "                    land[i][j]=-1\n",
    "                    while queue:\n",
    "                        k=len(queue)\n",
    "\n",
    "                        for _ in range (0,k):\n",
    "                            x,y=queue.pop(0)\n",
    "                            tem+=1\n",
    "                            for dx in [-1,0,1]:\n",
    "                                for dy in [-1,0,1]:\n",
    "                                    newx=x+dx\n",
    "                                    newy=y+dy\n",
    "                                    if 0<=newx<m and 0<=newy<n and land[newx][newy]==0:\n",
    "                                        queue.append([newx,newy])\n",
    "                                        land[newx][newy]=-1\n",
    "                    ans.append(tem)\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, land, i, j, ans):\n",
    "        m,n=len(land),len(land[0])\n",
    "        dir=((-1,0),(1,0),(0,-1),(0,1),(-1,1),(1,1),(1,-1),(-1,-1))\n",
    "        st=[(i,j)]\n",
    "        c=1\n",
    "        land[i][j]=1\n",
    "        while st:\n",
    "            x,y=st.pop()\n",
    "            for dx, dy in dir:\n",
    "                nx,ny=x+dx,y+dy\n",
    "                if 0<=nx<m and 0<=ny<n and land[nx][ny]==0:\n",
    "                    land[nx][ny]=1\n",
    "                    st.append((nx,ny))\n",
    "                    c+=1\n",
    "        ans.append(c)\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m,n=len(land),len(land[0])\n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]==0:\n",
    "                    self.dfs(land,i,j,ans)\n",
    "        return sorted(ans)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def isvaild (self, row:int, line: int, land: List[List[int]])-> bool:\n",
    "        \n",
    "        if row >= 0 and row < len(land) and line >= 0 and line < len(land[0]):\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def getzeroarea(self, row:int, line: int, land: List[List[int]], coveredlist: List[int], reslist:List[int]) -> None:\n",
    "        zeromap = [[0,  1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1]]\n",
    "        reslist.append([row, line])\n",
    "        #print (\"-----:\", reslist)\n",
    "        for i in range(len(zeromap)):\n",
    "            new_row = row + zeromap[i][0]\n",
    "            new_line = line + zeromap[i][1]\n",
    "            if self.isvaild(new_row, new_line, land) and self.getnextzero(new_row, new_line, land, coveredlist):\n",
    "                self.getzeroarea(new_row, new_line, land, coveredlist , reslist)\n",
    "   \n",
    "    def getnextzero(self, row:int, line: int, land: List[List[int]], coveredlist: List[int])-> bool:\n",
    "        tempvale = row * len(land[0]) + line\n",
    "        if land[row][line] == 0 and (tempvale not in coveredlist):\n",
    "            coveredlist.append(tempvale)\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        coveredlist = []\n",
    "        reslist = []\n",
    "        zerocount = []\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                tempres = self.getnextzero(i, j, land, coveredlist)\n",
    "                if tempres == False:\n",
    "                    continue\n",
    "                self.getzeroarea(i, j, land, coveredlist, reslist)\n",
    "                print (\"0000000:\", reslist)\n",
    "                zerocount. append(len(reslist))\n",
    "                reslist = []\n",
    "        zerocount.sort()\n",
    "        return zerocount\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        @cache\n",
    "        def bfs(x,y):\n",
    "            res = 0\n",
    "            q = deque([(x,y)])\n",
    "            land[x][y] = -1\n",
    "            while q:\n",
    "                x,y = q.popleft()\n",
    "                res += 1\n",
    "                for dx in [-1,0,1]:\n",
    "                    for dy in [-1,0,1]:\n",
    "                        if dx == dy == 0: continue\n",
    "                        x2 = x + dx\n",
    "                        y2 = y + dy\n",
    "                        if x2 <0 or y2 <0 or x2 >= m or y2 >= n:\n",
    "                            continue\n",
    "                        if land[x2][y2] == 0 :\n",
    "                            land[x2][y2] = -1\n",
    "                            q.append((x2,y2))\n",
    "\n",
    "            return res\n",
    "        \n",
    "        res_list = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    res_list.append(bfs(i,j))\n",
    "        res_list.sort()\n",
    "        return res_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        ans = []\n",
    "        direction = [[-1,-1], [1, 0], [-1, 0], [-1, 1], [0, -1], [1, -1], [0, 1], [1, 1]]\n",
    "\n",
    "        def bfs(i, j):\n",
    "            if any([not 0 <= i < m, not 0 <= j < n]):\n",
    "                return 0\n",
    "            if land[i][j] != 0:\n",
    "                return 0\n",
    "            land[i][j] = 1\n",
    "            l0.append(1)\n",
    "            for r, c in direction:\n",
    "                bfs(i + r, c + j)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                l0 = []\n",
    "                bfs(i, j)\n",
    "                if l0:\n",
    "                    bisect.insort_left(ans, sum(l0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        dir = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]\n",
    "        ans = []\n",
    "        m,n = len(land),len(land[0])\n",
    "        def delete(x,y):\n",
    "            land[x][y] = -1\n",
    "            tmp = 1\n",
    "            for dx,dy in dir:\n",
    "                new_x,new_y = x+dx,y+dy\n",
    "                if 0<=new_x<m and 0<=new_y<n and land[new_x][new_y] == 0:\n",
    "                    tmp+=delete(new_x,new_y)\n",
    "            return tmp\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    ans.append(delete(i,j))\n",
    "        ans.sort()\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        def f(x, y):\n",
    "            nonlocal tmp \n",
    "            if land[x][y] == 0:\n",
    "                tmp += 1\n",
    "                land[x][y] = -1\n",
    "                for nx, ny in (x+1, y), (x-1, y),(x, y+1),(x, y-1),(x-1, y-1),(x-1, y+1),(x+1, y+1),(x+1, y-1):\n",
    "                    if 0<=nx<m and 0<=ny<n:\n",
    "                        f(nx, ny)\n",
    "        m, n = len(land), len(land[0])\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    tmp = 0\n",
    "                    f(i, j)\n",
    "                    ans.append(tmp)\n",
    "\n",
    "        ans.sort()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        def dfs(r, c):\n",
    "            if r < 0 or r >= len(land) or c < 0 or c >= len(land[0]) or land[r][c] != 0:\n",
    "                return 0\n",
    "            size = 1\n",
    "            land[r][c] = -1  # 标记当前位置已访问\n",
    "            for dr in [-1, 0, 1]:\n",
    "                for dc in [-1, 0, 1]:\n",
    "                    size += dfs(r + dr, c + dc)\n",
    "            return size\n",
    "\n",
    "        pond_sizes = []\n",
    "        for r in range(len(land)):\n",
    "            for c in range(len(land[0])):\n",
    "                if land[r][c] == 0:\n",
    "                    pond_size = dfs(r, c)\n",
    "                    if pond_size > 0:\n",
    "                        pond_sizes.append(pond_size)\n",
    "\n",
    "        return sorted(pond_sizes)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if x < 0 or x >= m or y < 0 or y >= n or land[x][y] != 0:\n",
    "                return 0\n",
    "            \n",
    "            land[x][y] = -1\n",
    "            res = 1\n",
    "            for dx in [-1, 0, 1]:\n",
    "                for dy in [-1, 0, 1]:\n",
    "                    if dx == dy == 0:\n",
    "                        continue\n",
    "                    res += dfs(x + dx, y + dy)\n",
    "            return res\n",
    "        \n",
    "        res = list()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    res.append(dfs(i, j))\n",
    "        res.sort()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if x < 0 or x >= m or y < 0 or y >= n or land[x][y] != 0:\n",
    "                return 0\n",
    "            \n",
    "            land[x][y] = -1\n",
    "            res = 1\n",
    "            for dx in [-1, 0, 1]:\n",
    "                for dy in [-1, 0, 1]:\n",
    "                    if dx == dy == 0:\n",
    "                        continue\n",
    "                    res += dfs(x + dx, y + dy)\n",
    "            return res\n",
    "        \n",
    "        res = list()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    res.append(dfs(i, j))\n",
    "        res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        self.m = len(land)\n",
    "        self.n = len(land[0])\n",
    "        self.visited = [[False]*self.n for _ in range(self.m)]\n",
    "        self.land = land\n",
    "        result = []\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                if not self.visited[i][j] and not self.land[i][j] :\n",
    "                    result.append(self.dfs(i, j, 1))\n",
    "        result.sort()\n",
    "        return result\n",
    "    \n",
    "    def dfs(self, i, j, count):\n",
    "        self.visited[i][j] = True\n",
    "        dire = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]\n",
    "        for x, y in dire:\n",
    "            new_x = i+x\n",
    "            new_y = j+y \n",
    "            if new_x<0 or new_x>=self.m or new_y<0 or new_y>=self.n or self.visited[new_x][new_y]:\n",
    "                continue\n",
    "            elif self.land[new_x][new_y] == 0:\n",
    "                count = self.dfs(new_x, new_y, count+1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        self.map = [[0] * len(land[0]) for i in range(len(land))]\n",
    "        self.dicrection = [[0,-1],[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1]]\n",
    "        pool_num = 1\n",
    "        ans = []\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if self.map[i][j] == 0 and land[i][j] == 0:\n",
    "                    self.map[i][j] = pool_num\n",
    "                    ans.append(self.dfs(i,j,land) + 1)\n",
    "                    pool_num += 1\n",
    "        ans.sort()\n",
    "        return ans\n",
    "    \n",
    "    def dfs(self,x,y,land):\n",
    "        area = 0\n",
    "        for dx,dy in self.dicrection:\n",
    "            tar_x = x + dx\n",
    "            tar_y = y + dy\n",
    "            if 0<=tar_x<len(self.map) and 0<=tar_y<len(self.map[0]) and land[tar_x][tar_y] == 0 and self.map[tar_x][tar_y] == 0:\n",
    "                self.map[tar_x][tar_y] = self.map[x][y]\n",
    "                area += 1\n",
    "                area +=self.dfs(tar_x, tar_y, land)\n",
    "\n",
    "        return area\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        pond_sizes = []\n",
    "        grid = copy.deepcopy(land)\n",
    "        directions = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (1,-1), (-1, 1), (-1, -1)]\n",
    "        row, col = len(grid), len(grid[0])\n",
    "\n",
    "        def is_valid_loc(i, j):\n",
    "            return (0 <= i <= row-1) and (0 <= j <= col-1)\n",
    "\n",
    "        def bfs(start_loc):\n",
    "            size = 1\n",
    "            queue = [start_loc]\n",
    "            seen = set()\n",
    "            seen.add(start_loc)\n",
    "            while queue:\n",
    "                loc_i, loc_j = queue.pop(0)\n",
    "                for dir_i, dir_j in directions:\n",
    "                    nex_i, nex_j = loc_i + dir_i, loc_j + dir_j\n",
    "                    if is_valid_loc(nex_i, nex_j) and ((nex_i, nex_j) not in seen) and (grid[nex_i][nex_j] == 0):\n",
    "                        queue.append((nex_i, nex_j))\n",
    "                        grid[nex_i][nex_j] = -1\n",
    "                        size += 1\n",
    "                        seen.add((nex_i, nex_j))\n",
    "            return size\n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0:\n",
    "                    pond_sizes.append(bfs((i, j)))\n",
    "        \n",
    "        return sorted(pond_sizes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        ret = []\n",
    "        visited = set([])\n",
    "        search = []\n",
    "        dire = [[1, 0], [-1, 0], [0, 1], [0, -1], [-1, 1], [-1, -1], [1, -1], [1, 1]]\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] != 0 or i * n + j in visited:\n",
    "                    continue\n",
    "                search.append(i * n + j)\n",
    "                visited.add(i * n + j)\n",
    "                area = 1\n",
    "                while len(search) > 0:\n",
    "                    pos = search.pop(0)\n",
    "                    x = pos // n\n",
    "                    y = pos % n\n",
    "                    for k in range(8):\n",
    "                        new_x = x + dire[k][0]\n",
    "                        new_y = y + dire[k][1]\n",
    "                        if not new_x * n + new_y in visited and new_x >= 0 and new_x < m and new_y >= 0 and new_y < n and land[new_x][new_y] == 0:\n",
    "                            search.append(new_x * n + new_y)\n",
    "                            visited.add(new_x * n + new_y)\n",
    "                            area += 1\n",
    "                ret.append(area)\n",
    "        ret.sort()\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        def bfs(i, j):\n",
    "            nonlocal m, n\n",
    "            d = deque([(i, j)])\n",
    "            a = set([(i, j)])\n",
    "            while d:\n",
    "                x, y = d.popleft()\n",
    "\n",
    "                for dx in range(-1, 2):\n",
    "                    for dy in range(-1, 2):\n",
    "                        x_, y_ = x + dx, y + dy\n",
    "                        if 0 <= x_ < m and 0 <= y_ < n and land[x_][y_] == 0 and (x_, y_) not in a:\n",
    "                            d.append((x_, y_))\n",
    "                            a.add((x_, y_))\n",
    "            return a\n",
    "\n",
    "        m, n = len(land), len(land[0])\n",
    "        \n",
    "        asked = set()\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in asked and land[i][j] == 0:\n",
    "                    a = bfs(i, j)\n",
    "                    asked.update(a)\n",
    "                    insort(ans, len(a))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        dirs = [\n",
    "            [0, 1],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [-1, 0],\n",
    "            [1, 1],\n",
    "            [-1, -1],\n",
    "            [-1, 1],\n",
    "            [1, -1]\n",
    "        ]\n",
    "\n",
    "        rows = len(land)\n",
    "        cols = len(land[0])\n",
    "\n",
    "        def dfs(x, y, area):\n",
    "            for d in dirs:\n",
    "                nx = x + d[0]\n",
    "                ny = y + d[1]\n",
    "                if nx < 0 or ny < 0 or nx >= rows or ny >= cols:\n",
    "                    continue \n",
    "                \n",
    "                if visited[nx][ny] == False:\n",
    "                    if land[nx][ny] == 0:\n",
    "                        area[0] += 1\n",
    "                        visited[nx][ny] = True \n",
    "                        dfs(nx, ny, area)\n",
    "\n",
    "        res = []\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if visited[r][c] == False:\n",
    "                    if land[r][c] == 0:\n",
    "                        visited[r][c] = True \n",
    "                        area = [1]\n",
    "                        dfs(r, c, area)\n",
    "                        res.append(area[0])\n",
    "        \n",
    "        # print(res) \n",
    "        res.sort()\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def qSort(self, arr, l, r):\n",
    "        if l >= r:\n",
    "            return \n",
    "        piv_idx = random.randint(l, r)\n",
    "        piv = arr[piv_idx]\n",
    "\n",
    "        arr[l], arr[piv_idx] = arr[piv_idx], arr[l]\n",
    "\n",
    "        i = l + 1 \n",
    "        j = l \n",
    "        k = r + 1 \n",
    "        while i < k:\n",
    "            if arr[i] < piv:\n",
    "                arr[i], arr[j+1] = arr[j+1], arr[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif arr[i] > piv:\n",
    "                arr[i], arr[k-1] = arr[k-1], arr[i]\n",
    "                k -= 1 \n",
    "            else:\n",
    "                i += 1 \n",
    "        \n",
    "        arr[l], arr[j] = arr[j], arr[l]\n",
    "        self.qSort(arr, l, j-1)\n",
    "        self.qSort(arr, k, r)\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        dirs = [\n",
    "            [0, 1],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [-1, 0],\n",
    "            [1, 1],\n",
    "            [-1, -1],\n",
    "            [-1, 1],\n",
    "            [1, -1]\n",
    "        ]\n",
    "\n",
    "        rows = len(land)\n",
    "        cols = len(land[0])\n",
    "\n",
    "        def dfs(x, y, area):\n",
    "            for d in dirs:\n",
    "                nx = x + d[0]\n",
    "                ny = y + d[1]\n",
    "                if nx < 0 or ny < 0 or nx >= rows or ny >= cols:\n",
    "                    continue \n",
    "                \n",
    "                if visited[nx][ny] == False:\n",
    "                    if land[nx][ny] == 0:\n",
    "                        area[0] += 1\n",
    "                        visited[nx][ny] = True \n",
    "                        dfs(nx, ny, area)\n",
    "\n",
    "        res = []\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if visited[r][c] == False:\n",
    "                    if land[r][c] == 0:\n",
    "                        visited[r][c] = True \n",
    "                        area = [1]\n",
    "                        dfs(r, c, area)\n",
    "                        res.append(area[0])\n",
    "        \n",
    "        # print(res) \n",
    "        self.qSort(res, 0, len(res)-1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def qSort(self, arr, l, r):\n",
    "        if l >= r:\n",
    "            return \n",
    "        piv_idx = random.randint(l, r)\n",
    "        piv = arr[piv_idx]\n",
    "\n",
    "        arr[l], arr[piv_idx] = arr[piv_idx], arr[l]\n",
    "\n",
    "        i = l + 1 \n",
    "        j = l \n",
    "        k = r + 1 \n",
    "        while i < k:\n",
    "            if arr[i] < piv:\n",
    "                arr[i], arr[j+1] = arr[j+1], arr[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif arr[i] > piv:\n",
    "                arr[i], arr[k-1] = arr[k-1], arr[i]\n",
    "                k -= 1 \n",
    "            else:\n",
    "                i += 1 \n",
    "        \n",
    "        arr[l], arr[j] = arr[j], arr[l]\n",
    "        self.qSort(arr, l, j-1)\n",
    "        self.qSort(arr, k, r)\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        dirs = [\n",
    "            [0, 1],\n",
    "            [1, 0],\n",
    "            [0, -1],\n",
    "            [-1, 0],\n",
    "            [1, 1],\n",
    "            [-1, -1],\n",
    "            [-1, 1],\n",
    "            [1, -1]\n",
    "        ]\n",
    "\n",
    "        rows = len(land)\n",
    "        cols = len(land[0])\n",
    "\n",
    "        def dfs(x, y, area):\n",
    "            for d in dirs:\n",
    "                nx = x + d[0]\n",
    "                ny = y + d[1]\n",
    "                if nx < 0 or ny < 0 or nx >= rows or ny >= cols:\n",
    "                    continue \n",
    "                \n",
    "                if visited[nx][ny] == False:\n",
    "                    if land[nx][ny] == 0:\n",
    "                        area[0] += 1\n",
    "                        visited[nx][ny] = True \n",
    "                        dfs(nx, ny, area)\n",
    "\n",
    "        res = []\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if visited[r][c] == False:\n",
    "                    if land[r][c] == 0:\n",
    "                        visited[r][c] = True \n",
    "                        area = [1]\n",
    "                        dfs(r, c, area)\n",
    "                        res.append(area[0])\n",
    "        \n",
    "        # print(res) \n",
    "        self.qSort(res, 0, len(res)-1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        def bfs(i, j, vis):\n",
    "            st = len(vis)\n",
    "            vis.add((i, j))\n",
    "            q = deque([(i, j)])\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]:\n",
    "                    nx = x + dx\n",
    "                    ny = y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in vis and land[nx][ny] == 0:\n",
    "                        q.append((nx, ny))\n",
    "                        vis.add((nx, ny))\n",
    "            return len(vis) - st, vis\n",
    "        \n",
    "        v = set()\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0 and (i, j) not in v:\n",
    "                    sz, v = bfs(i, j, v)\n",
    "                    res.append(sz)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def has_point(self, pond_list: list, e: tuple):\n",
    "        for pond in pond_list:\n",
    "            if e in pond:\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "    def find_pond(self, pond_list: list, e: tuple):\n",
    "        same_pond_list = []\n",
    "        for i, pond in enumerate(pond_list):\n",
    "            for p in pond:\n",
    "                if abs(e[0] - p[0]) <= 1 and abs(e[1] - p[1]) <= 1:\n",
    "                    same_pond_list.append(i)\n",
    "                    break\n",
    "        if len(same_pond_list) == 0:\n",
    "            return None\n",
    "        pond_idx = same_pond_list[0]\n",
    "        pond = pond_list[pond_idx]\n",
    "        for i in same_pond_list[1:]:\n",
    "            p = pond_list[i]\n",
    "            pond.update(p)\n",
    "            pond_list.remove(p)\n",
    "        return pond\n",
    "    \n",
    "    def pondSizes_bad(self, land: List[List[int]]) -> List[int]:\n",
    "        pond_list = []\n",
    "        col_len = len(land)\n",
    "        for i in range(col_len):\n",
    "            row = land[i]\n",
    "            # print(len(row))\n",
    "            # print(row)\n",
    "            row_len = len(row)\n",
    "            for j in range(row_len):\n",
    "                if row[j] == 0:\n",
    "                    e = (i, j)\n",
    "                    pond = self.find_pond(pond_list, e)\n",
    "                    if pond is None:\n",
    "                        pond = {e}\n",
    "                        pond_list.append(pond)\n",
    "                    else:\n",
    "                        pond.add(e)\n",
    "\n",
    "        return sorted([len(pond) for pond in pond_list])\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        pond_list = []\n",
    "        col_len = len(land)\n",
    "        for ei in range(col_len):\n",
    "            row = land[ei]\n",
    "            row_len = len(row)\n",
    "            for ej in range(row_len):\n",
    "                if row[ej] == 0:\n",
    "                    e = (ei, ej)\n",
    "                    if self.has_point(pond_list, e):\n",
    "                        continue\n",
    "                    pond = {e}\n",
    "                    check_list = [e]\n",
    "                    while len(check_list) > 0:\n",
    "                        (i, j) = check_list.pop()\n",
    "                        for xi in (i-1, i, i+1):\n",
    "                            for xj in (j-1, j, j+1):\n",
    "                                if xi < 0 or xj < 0 or xi >= col_len or xj >= row_len:\n",
    "                                    continue\n",
    "                                xe = (xi, xj)\n",
    "                                if land[xi][xj] == 0 and xe not in pond:\n",
    "                                    pond.add(xe)\n",
    "                                    check_list.append(xe)\n",
    "                            # end for\n",
    "                        # end for\n",
    "                    # end while\n",
    "                    pond_list.append(pond)\n",
    "                # end if\n",
    "            # end for\n",
    "        # end for\n",
    "        return sorted([len(pond) for pond in pond_list])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        if not land or not land[0]:\n",
    "            return 0\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "\n",
    "        area = m * n\n",
    "        id = [-1] * area\n",
    "        sz = [1] * area\n",
    "\n",
    "        def ufind(p):\n",
    "            x = p\n",
    "            while x != id[x]:\n",
    "                x = id[x]\n",
    "            while True:\n",
    "                pnext = id[p]\n",
    "                if pnext == x:\n",
    "                    break\n",
    "                id[p] = x\n",
    "                p = pnext\n",
    "            return x\n",
    "\n",
    "        def un(p, q):\n",
    "            pid = ufind(p)\n",
    "            qid = ufind(q)\n",
    "            if pid != qid:\n",
    "                if sz[pid] < sz[qid]:\n",
    "                    sz[qid] += sz[pid]\n",
    "                    id[pid] = qid\n",
    "                else:\n",
    "                    sz[pid] += sz[qid]\n",
    "                    id[qid] = pid\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] != 0:\n",
    "                    continue\n",
    "                index = i * n + j\n",
    "                id[index] = index\n",
    "                if i > 0 and land[i - 1][j] == 0:\n",
    "                    un(index - n, index)\n",
    "                if j > 0 and land[i][j - 1] == 0:\n",
    "                    un(index - 1, index)\n",
    "                if i > 0 and j > 0 and land[i - 1][j - 1] == 0:\n",
    "                    un(index - n - 1, index)\n",
    "                if i > 0 and j + 1 < n and land[i - 1][j + 1] == 0:\n",
    "                    un(index - n + 1, index)\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        for i, (cid, csz) in enumerate(zip(id, sz)):\n",
    "            if i == cid:\n",
    "                ans.append(csz)\n",
    "\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        st = list()\n",
    "        ans = []\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if land[i][j] == 0:\n",
    "                    st.append([i,j])\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            t = 0\n",
    "            for dx in range(-1,2,1):\n",
    "                for dy in range(-1,2,1):\n",
    "                    i2 = i + dx\n",
    "                    j2 = j + dy\n",
    "                    if 0<=i2<len(land) and 0<=j2<len(land[0]):\n",
    "                        if land[i2][j2] == 0:\n",
    "                            land[i2][j2] = -1\n",
    "                            t += dfs(i2,j2) + 1\n",
    "            return t\n",
    "        for i,j in st:\n",
    "            if land[i][j] == 0:\n",
    "                land[i][j] = -1\n",
    "                ans.append(1 + dfs(i,j))\n",
    "\n",
    "        ans.sort()\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        parents = list(range(m * n + 1))\n",
    "        地の果て = m * n\n",
    "        \n",
    "        def find(x):\n",
    "            while x != parents[x]:\n",
    "                parents[x] = x = parents[parents[x]]\n",
    "            return x\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]:\n",
    "                    parents[i * n + j] = 地の果て\n",
    "                else:\n",
    "                    r = find(i * n + j)\n",
    "                    for nx, ny in ((i + 1, j), (i, j + 1), (i + 1, j + 1), (i + 1, j - 1)):\n",
    "                        if nx < m and 0 <= ny < n and not land[nx][ny]:\n",
    "                            parents[find(nx * n + ny)] = r\n",
    "        \n",
    "        book = defaultdict(int)\n",
    "        for i in range(m * n):\n",
    "            if (r := find(i)) != 地の果て:\n",
    "                book[r] += 1\n",
    "        return sorted(book.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        res = []\n",
    "        land = [[1 for i in range(n+2)]] + [[1]+j+[1] for j in land] + [[1 for i in range(n+2)]]\n",
    "        flag = [[True for i in range(n+2)] for j in range(m+2)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if flag[i][j] and land[i][j] == 0:\n",
    "                    res_acc = 1\n",
    "                    flag[i][j] = False\n",
    "                    q = [(i, j)]\n",
    "                    while q:\n",
    "                        row, col = heapq.heappop(q)\n",
    "                        if flag[row-1][col] and land[row-1][col] == 0:\n",
    "                            q.append((row-1, col))\n",
    "                            flag[row-1][col] = False\n",
    "                            res_acc += 1\n",
    "                        if flag[row-1][col+1] and land[row-1][col+1] == 0:\n",
    "                            q.append((row-1, col+1))\n",
    "                            flag[row-1][col+1] = False\n",
    "                            res_acc += 1\n",
    "                        if flag[row][col+1] and land[row][col+1] == 0:\n",
    "                            q.append((row, col+1))\n",
    "                            flag[row][col+1] = False\n",
    "                            res_acc += 1\n",
    "                        if flag[row+1][col+1] and land[row+1][col+1] == 0:\n",
    "                            q.append((row+1, col+1))\n",
    "                            flag[row+1][col+1] = False\n",
    "                            res_acc += 1\n",
    "                        if flag[row+1][col] and land[row+1][col] == 0:\n",
    "                            q.append((row+1, col))\n",
    "                            flag[row+1][col] = False\n",
    "                            res_acc += 1\n",
    "                        if flag[row+1][col-1] and land[row+1][col-1] == 0:\n",
    "                            q.append((row+1, col-1))\n",
    "                            flag[row+1][col-1] = False\n",
    "                            res_acc += 1\n",
    "                        if flag[row][col-1] and land[row][col-1] == 0:\n",
    "                            q.append((row, col-1))\n",
    "                            flag[row][col-1] = False\n",
    "                            res_acc += 1\n",
    "                        if flag[row-1][col-1] and land[row-1][col-1] == 0:\n",
    "                            q.append((row-1, col-1))\n",
    "                            flag[row-1][col-1] = False\n",
    "                            res_acc += 1\n",
    "                    res.append(res_acc)\n",
    "        return sorted(res)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land0: List[List[int]]) -> List[int]:\n",
    "        hight0 = len(land0)\n",
    "        width0 = len((land0[0]))\n",
    "        hight = hight0+2\n",
    "        width = width0+2\n",
    "\n",
    "        land = [[1]*(width) for i in range(hight)]\n",
    "        for i in range(1, hight-1):\n",
    "            for j in range(1, width-1):\n",
    "                land[i][j] = land0[i-1][j-1]\n",
    "        \n",
    "\n",
    "        num_island = 0\n",
    "        result = []\n",
    "        def bfs(i,j):\n",
    "            nonlocal mj\n",
    "            nonlocal land\n",
    "            if land[i][j]==0:\n",
    "                mj+=1\n",
    "                land[i][j]=1\n",
    "                # print(land)\n",
    "            for diff_i in range(0,3):\n",
    "                for diff_j in range(0,3):\n",
    "                    if diff_i==1 and diff_j==1:\n",
    "                        continue\n",
    "                    if land[i+diff_i-1][j+diff_j-1]==0:\n",
    "                        # print('Diffused')\n",
    "                        bfs(i+diff_i-1,j+diff_j-1)\n",
    "\n",
    "        print(land)\n",
    "        for i in range(hight):\n",
    "            for j in range(width):\n",
    "                if land[i][j]!= 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    num_island += 1\n",
    "                    mj = 0\n",
    "                    bfs(i,j)\n",
    "                    # print('New island')\n",
    "                    # print(land)\n",
    "                    result.append(mj)\n",
    "        result.sort()\n",
    "        return result\n",
    "                \n",
    "        \n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n, wid, lstd, dct = len(land) + 2, len(land[0]) + 2, 1, [(0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1)], defaultdict(list)\n",
    "        land = [[-1] * n] + [[-1] + [-1 if c else 0 for c in row] + [-1] for row in land] + [[-1] * n]\n",
    "        #print(land)\n",
    "        for r in range(1, m - 1):\n",
    "            for c in range(1, n - 1):\n",
    "                if land[r][c]: continue                \n",
    "                if se := set([land[r + i][c + j] for i, j in lstd]) - {-1, 0}: \n",
    "                    #print(r, c, land, dct)\n",
    "                    land[r][c] = se.pop()  \n",
    "                    dct[land[r][c]].append((r, c))  \n",
    "                    for s in se:\n",
    "                        #for i in range(r - 1, r + 1):\n",
    "                        #    for j in range(1, n - 1):\n",
    "                        #        if land[i][j] == s: land[i][j] = land[r][c]  \n",
    "                        for j in range(c, n - 1): \n",
    "                            if land[r - 1][j] == s: land[r - 1][j] = land[r][c]     \n",
    "                        for j in range(1, c):\n",
    "                            if land[r][j] == s: land[r][j] = land[r][c]    \n",
    "                        #for i, j in dct[s]: land[i][j] = land[r][c]\n",
    "                        dct[land[r][c]] += dct[s]\n",
    "                        dct.pop(s)\n",
    "                    #print(r, c, land, dct)\n",
    "                    #for s in se:\n",
    "                    #    for i in range(1, r + 1):\n",
    "                    #        for j in range(1, n - 1):\n",
    "                    #            if land[i][j] == s: land[i][j] = land[r][c]\n",
    "                else:\n",
    "                    land[r][c] = wid\n",
    "                    dct[wid].append((r, c))\n",
    "                    wid += 1   \n",
    "        #print(land)\n",
    "        #print(dct)\n",
    "        return sorted(map(len, dct.values()))\n",
    "        #return sorted(Counter(w for w in sum(land, []) if w != -1).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n, wid, lstd, dct = len(land) + 2, len(land[0]) + 2, 1, [(0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1)], defaultdict(list)\n",
    "        land = [[-1] * n] + [[-1] + [-1 if c else 0 for c in row] + [-1] for row in land] + [[-1] * n]\n",
    "        #print(land)\n",
    "        for r in range(1, m - 1):\n",
    "            for c in range(1, n - 1):\n",
    "                if land[r][c]: continue                \n",
    "                if se := set([land[r + i][c + j] for i, j in lstd]) - {-1, 0}: \n",
    "                    #print(r, c, land, dct)\n",
    "                    land[r][c] = se.pop()  \n",
    "                    dct[land[r][c]].append((r, c))  \n",
    "                    for s in se:\n",
    "                        #for i in range(r - 1, r + 1):\n",
    "                        #    for j in range(1, n - 1):\n",
    "                        #        if land[i][j] == s: land[i][j] = land[r][c]  \n",
    "                        for j in range(c, n - 1): \n",
    "                            if land[r - 1][j] == s: land[r - 1][j] = land[r][c]     \n",
    "                        for j in range(1, c):\n",
    "                            if land[r][j] == s: land[r][j] = land[r][c]    \n",
    "                        #for i, j in dct[s]: land[i][j] = land[r][c]\n",
    "                        dct[land[r][c]] += dct[s]\n",
    "                        dct.pop(s)\n",
    "                    #print(r, c, land, dct)\n",
    "                    #for s in se:\n",
    "                    #    for i in range(1, r + 1):\n",
    "                    #        for j in range(1, n - 1):\n",
    "                    #            if land[i][j] == s: land[i][j] = land[r][c]\n",
    "                else:\n",
    "                    land[r][c] = wid\n",
    "                    dct[wid].append((r, c))\n",
    "                    wid += 1   \n",
    "        #print(land)\n",
    "        #print(dct)\n",
    "        return sorted(map(len, dct.values()))\n",
    "        #return sorted(Counter(w for w in sum(land, []) if w != -1).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        dirs = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]\n",
    "        def dfs(i, j):\n",
    "            land[i][j] = 1\n",
    "            path.append([i, j])\n",
    "            for dir in dirs:\n",
    "                new_i = dir[0] + i \n",
    "                new_j = dir[1] + j \n",
    "                if 0 <= new_i < m and 0 <= new_j < n and land[new_i][new_j] == 0:\n",
    "                    dfs(new_i, new_j)\n",
    "        \n",
    "        m, n = len(land), len(land[0])\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    path = []   \n",
    "                    dfs(i, j)\n",
    "                    res.append(path)\n",
    "        ans = [len(_) for _ in res]\n",
    "        return sorted(ans)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, small, large):\n",
    "        small_l = self.record[small]\n",
    "        for i, j in small_l:\n",
    "            self.number_land[i][j] = large\n",
    "        self.record.pop(small)\n",
    "        self.record[large].extend(small_l)\n",
    "        return large\n",
    "\n",
    "    def judge(self, i, j):\n",
    "        conti = set()\n",
    "        if i - 1 >= 0 and self.number_land[i-1][j] != 0: # 左边有池塘\n",
    "            conti.add(self.number_land[i-1][j])\n",
    "        if j - 1 >= 0 and self.number_land[i][j-1] != 0: # 上面有池塘\n",
    "            conti.add(self.number_land[i][j-1])\n",
    "        if i-1>=0 and j-1>=0 and self.number_land[i-1][j-1] != 0: # 左上有池塘\n",
    "            conti.add(self.number_land[i-1][j-1])\n",
    "        if i-1 >=0 and j+1 < len(self.number_land[0]) and self.number_land[i-1][j+1]: # 右上有池塘\n",
    "            conti.add(self.number_land[i-1][j+1])\n",
    "        if len(conti) == 0: # 与之前的池塘不相连，为新池塘\n",
    "            self.number_land[i][j] = self.cnt\n",
    "            self.record[self.cnt] = [(i, j)]\n",
    "            self.cnt += 1\n",
    "        elif len(conti) == 1: # 只与一个池塘相连\n",
    "            num = conti.pop()\n",
    "            self.number_land[i][j] = num\n",
    "            self.record[num].append((i,j))\n",
    "        else: # 与不止一个池塘相连，但最多有两种不同的池塘\n",
    "            num1 = conti.pop()\n",
    "            num2 = conti.pop()\n",
    "            num1_l = self.record[num1]\n",
    "            num2_l = self.record[num2]\n",
    "            # 小池塘向大池塘合并\n",
    "            if len(num1_l) <= len(num2_l):\n",
    "                cur_num = self.merge(num1, num2) # num1 向 num2 合并\n",
    "            else:\n",
    "                cur_num = self.merge(num2, num1)\n",
    "            self.number_land[i][j] = cur_num\n",
    "            self.record[cur_num].append((i,j))\n",
    "\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        l, h = len(land), len(land[0])\n",
    "        self.number_land = [[0]*h for _ in range(l)]\n",
    "        self.cnt = 1\n",
    "        self.record = {}\n",
    "        for i in range(l):\n",
    "            for j in range(h):\n",
    "                if land[i][j] != 0:\n",
    "                    continue\n",
    "                self.judge(i,j)\n",
    "        sort_l = sorted(self.record.items(), key=lambda x:len(x[1]))\n",
    "        return [len(x[1]) for x in sort_l]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arrow = [[1, 0],[-1, 0],[0, 1],[0, -1],[1, -1],[1, 1],[-1, -1],[-1, 1]]\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        n, m = len(land), len(land[0])\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or i >= n or j < 0 or j >= m or land[i][j] != 0: return 0\n",
    "            land[i][j] = 1\n",
    "            return sum(dfs(i +a, j + b) for a, b in [[1, 0],[-1, 0],[0, 1],[0, -1],[1, -1],[1, 1],[-1, -1],[-1, 1]]) + 1\n",
    "\n",
    "        return sorted(filter(lambda x: x, [dfs(i, j) for j in range(m) for i in range(n)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m,n=len(land),len(land[0])\n",
    "        waters=[(i,j) for i in range(m) for j in range(n) if land[i][j]==0]\n",
    "        seen=set()\n",
    "\n",
    "        def dfs(i,j):\n",
    "            res=1\n",
    "            seen.add((i,j))\n",
    "            for x,y in zip([i-1,i-1,i-1,i,i,i+1,i+1,i+1],[j-1,j,j+1,j-1,j+1,j-1,j,j+1]):\n",
    "                if 0<=x<m and 0<=y<n and land[x][y]==0 and (x,y) not in seen:\n",
    "                    res+=dfs(x,y)\n",
    "                    seen.add((x,y))\n",
    "            return res\n",
    "        res=[]\n",
    "        for water in waters:\n",
    "            if water not in seen:\n",
    "                i,j=water\n",
    "                res.append(dfs(i,j))\n",
    "        res.sort()\n",
    "        return res\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        # init pool map\n",
    "        m,n =len(land),len(land[0])\n",
    "        pool_map = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        visited = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        # dp \n",
    "        def get_pool_size(i,j):\n",
    "            \n",
    "            if i < 0 or i >= m or j < 0 or j >= n:\n",
    "                return 0\n",
    "\n",
    "            if land[i][j] != 0:\n",
    "                return 0\n",
    "            if visited[i][j]:\n",
    "                return 0\n",
    "\n",
    "            total_pond = 0\n",
    "            visited[i][j]=1\n",
    "            \n",
    "            total_pond += 1\n",
    "            total_pond += get_pool_size(i-1,j-1)\n",
    "            total_pond += get_pool_size(i-1,j)\n",
    "            total_pond += get_pool_size(i-1,j+1)\n",
    "\n",
    "            total_pond += get_pool_size(i,j-1)\n",
    "            total_pond += get_pool_size(i,j+1)\n",
    "\n",
    "            total_pond += get_pool_size(i+1,j-1)\n",
    "            total_pond += get_pool_size(i+1,j)\n",
    "            total_pond += get_pool_size(i+1,j+1)\n",
    "            return total_pond\n",
    "        sizes = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0 and land[i][j] == 0:\n",
    "                    one_pool = get_pool_size(i,j)\n",
    "                    sizes.append(one_pool)\n",
    "        sizes.sort()\n",
    "        return sizes\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m,n=len(land),len(land[0])\n",
    "        visited=[[0]*n for i in range(m)]\n",
    "\n",
    "        x=[0,1,-1]\n",
    "        y=[0,1,-1]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            nonlocal cur\n",
    "            if visited[i][j]:\n",
    "                return\n",
    "            cur+=1\n",
    "            visited[i][j]=1\n",
    "            for dx in x:\n",
    "                for dy in y:\n",
    "                    if dx==0 and dy==0:\n",
    "                        continue\n",
    "                    nx=i+dx\n",
    "                    ny=j+dy\n",
    "                    if 0<=nx<m and 0<=ny<n and not visited[nx][ny] and land[nx][ny]==0:\n",
    "                        dfs(nx,ny)\n",
    "        \n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j]==0 and not visited[i][j]:\n",
    "                    cur=0\n",
    "                    dfs(i,j)\n",
    "                    ans.append(cur)\n",
    "        return sorted(ans)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        池塘：0连接在一起，就能构成池塘。 1个0也算池塘\n",
    "        dfs 广度优先算法：\n",
    "            1. 设置一个二维数组标记某个点是否访问过\n",
    "            2. 从0,0点开始for循环每个节点，如果不是0就continue, 标记为已访问，如果是0，就标记为一访问，获得他的邻居\n",
    "                2.1 邻居如果是0，标记已访问, 然后继续搜索他的邻kk居, 返回长度 邻居的长度 + 1\n",
    "\n",
    "        '''\n",
    "\n",
    "        rows, cols = len(land), len(land[0])\n",
    "        visit = [[False for j in range(len(land[0]))] for i in range(rows)]\n",
    "        print(visit)\n",
    "\n",
    "        # 0,0 \n",
    "        wz = [(i,j) for j in [-1,0,1] for i in [-1,0,1]]\n",
    "        print(f\"wz:{wz}\")\n",
    "        def dfs(i, j):\n",
    "            visit[i][j] = True\n",
    "            if land[i][j] != 0:\n",
    "                return 0\n",
    "            \n",
    "            num = 1\n",
    "            for x,y in wz:\n",
    "                if i+x >= 0 and i+x < rows and j+y >= 0 and  j+y < cols and visit[i+x][j+y] == False:\n",
    "                    num += dfs(i+x, j+y)\n",
    "\n",
    "            return num\n",
    "            \n",
    "        ctdx = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if land[i][j] == 0 and visit[i][j] == False:\n",
    "                    ctdx.append(dfs(i, j))\n",
    "        \n",
    "        return sorted(list([i for i in ctdx if i != 0]))\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        池塘：0连接在一起，就能构成池塘。 1个0也算池塘\n",
    "        dfs 广度优先算法：\n",
    "            1. 设置一个二维数组标记某个点是否访问过\n",
    "            2. 从0,0点开始for循环每个节点，如果不是0就continue, 标记为已访问，如果是0，就标记为一访问，获得他的邻居\n",
    "                2.1 邻居如果是0，标记已访问, 然后继续搜索他的邻kk居, 返回长度 邻居的长度 + 1\n",
    "\n",
    "        '''\n",
    "\n",
    "        rows, cols = len(land), len(land[0])\n",
    "        visit = [[False for j in range(len(land[0]))] for i in range(rows)]\n",
    "        print(visit)\n",
    "\n",
    "        # 0,0 \n",
    "        wz = [(i,j) for j in [-1,0,1] for i in [-1,0,1]]\n",
    "        print(f\"wz:{wz}\")\n",
    "        def dfs(i, j):\n",
    "            # print(f\"dfs,i:{i},j:{j}\")\n",
    "            visit[i][j] = True\n",
    "            if land[i][j] != 0:\n",
    "                return 0\n",
    "            \n",
    "            num = 1\n",
    "            for x,y in wz:\n",
    "                # print(f\"x:{x},y:{y},i,j:{i}{j}\")\n",
    "                if i+x >= 0 and i+x < rows and j+y >= 0 and  j+y < cols and visit[i+x][j+y] == False:\n",
    "                    num += dfs(i+x, j+y)\n",
    "\n",
    "            return num\n",
    "            \n",
    "        ctdx = []\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if land[i][j] == 0 and visit[i][j] == False:\n",
    "                    ctdx.append(dfs(i, j))\n",
    "        \n",
    "        print(\"ctds:\", ctdx)\n",
    "        result = sorted(list([i for i in ctdx if i != 0]))\n",
    "        print(\"ctds:\", result)\n",
    "        return result\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        visited=set()\n",
    "        m=len(land)\n",
    "        n=len(land[0])\n",
    "        def dfs(land,i,j):\n",
    "            visited.add((i,j))\n",
    "            water_num=1\n",
    "            for i_,j_ in [[i+1,j],[i-1,j],[i+1,j+1],[i+1,j-1],[i-1,j+1],[i-1,j-1],[i,j+1],[i,j-1]]:\n",
    "                if 0<=i_<m and 0<=j_<n and (i_,j_) not in visited and land[i_][j_]==0:\n",
    "                    water_num+=dfs(land, i_, j_)\n",
    "            return water_num\n",
    "        res=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i,j) not in visited and land[i][j]==0:\n",
    "                    res.append(dfs(land, i, j))\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        row = len(land)\n",
    "        col = len(land[0])\n",
    "        \n",
    "        di = dict()\n",
    "\n",
    "        def find(x):\n",
    "            if di[x] == x:\n",
    "                return x\n",
    "            return find(di[x])\n",
    "\n",
    "        def uni(x, y):\n",
    "            di[find(x)] = find(y)\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if land[i][j] == 0:\n",
    "                    di[(i, j)] = (i, j)\n",
    "        for (i, j) in di:\n",
    "            if (i, j-1) in di:\n",
    "                uni((i, j-1), (i, j))\n",
    "            if (i-1, j-1) in di:\n",
    "                uni((i-1, j-1), (i, j))\n",
    "            if (i-1, j) in di:\n",
    "                uni((i-1, j), (i, j))\n",
    "            if (i-1, j+1) in di:\n",
    "                uni((i-1, j+1), (i, j))\n",
    "        \n",
    "        res = dict()\n",
    "        for i in di:\n",
    "            if find(i) not in res:\n",
    "                res[find(i)] = 1\n",
    "            else:\n",
    "                res[find(i)] += 1\n",
    "\n",
    "        res = list(res.values())\n",
    "        res.sort()\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        visited = [[0] * len(land[0]) for i in range(len(land))]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if not 0<= i < len(land) or not 0<= j < len(land[0]) or visited[i][j] == 1 or land[i][j] > 0:  return 0\n",
    "\n",
    "            c = 1\n",
    "            visited[i][j] = 1\n",
    "            c += dfs(i-1, j-1)\n",
    "            c += dfs(i-1, j)\n",
    "            c += dfs(i-1, j+1)\n",
    "            c += dfs(i, j-1)\n",
    "            c += dfs(i, j+1)\n",
    "            c += dfs(i+1, j-1)\n",
    "            c += dfs(i+1, j)\n",
    "            c += dfs(i+1, j+1)\n",
    "            return c\n",
    "\n",
    "\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if visited[i][j] == 0 and land[i][j] == 0:\n",
    "                    res.append(dfs(i, j))\n",
    "        return sorted(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        vis = [[0]*len(land[0]) for _ in range(len(land))]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if i<0 or j<0 or i>=len(land) or j >= len(land[0]) or vis[i][j] or land[i][j]:\n",
    "                return 0\n",
    "            vis[i][j] = 1\n",
    "            cnt = 1\n",
    "            for dx in [-1,0,1]:\n",
    "                for dy in [-1,0,1]:\n",
    "                    cnt += dfs(i+dx,j+dy)\n",
    "            return cnt\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if not vis[i][j] and not land[i][j]:\n",
    "                    ans.append(dfs(i,j))\n",
    "\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        is_visited = [[False for _ in range(len(land[0]))] for _ in range(len(land))]\n",
    "        def dfs(i, j):\n",
    "            if 0 <= i < len(land) and 0 <= j < len(land[0]) and is_visited[i][j] == False and land[i][j] == 0:\n",
    "                #print(i, j)\n",
    "                v = 1\n",
    "                is_visited[i][j] = True\n",
    "                #print(is_visited[0][0])\n",
    "                a = dfs(i + 1, j)\n",
    "                b = dfs(i, j + 1)\n",
    "                c = dfs(i + 1, j + 1)\n",
    "                d = dfs(i, j - 1)\n",
    "                e = dfs(i - 1, j - 1)\n",
    "                f = dfs(i + 1, j - 1)\n",
    "                g = dfs(i - 1, j + 1)\n",
    "                h = dfs(i - 1, j)\n",
    "                return v + a + b + c + d + e + f + g + h\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        ans = []\n",
    "        \n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if is_visited[i][j] == False and land[i][j] == 0:\n",
    "                    ans.append(dfs(i, j))\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        b = []\n",
    "        ch = len(land[0])\n",
    "        ku = len(land)\n",
    "        def check(i,j,now):\n",
    "            if i>-1 and j>-1 and  i < ku and j<ch and land[i][j]==0 and [i,j] not in now:\n",
    "                now.append([i,j])\n",
    "                a.append([i,j])\n",
    "                for x in [-1,0,1]:\n",
    "                    for y in [-1,0,1]:\n",
    "                        # if [x,y] != [0,0]:\n",
    "                        check(i+x,j+y,now)\n",
    "        for i in range(ku):\n",
    "            for j in range(ch):\n",
    "                if land[i][j]==0 and [i,j] not in a:\n",
    "                    now = []\n",
    "                    check(i,j, now)\n",
    "                    print(now)\n",
    "                    if now:\n",
    "                        b.append(len(now))\n",
    "        print(b)\n",
    "        # b = [bb for bb in b if bb>0]\n",
    "        return sorted(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        b = []\n",
    "        ch = len(land[0])\n",
    "        ku = len(land)\n",
    "        def check(i,j,now):\n",
    "            if i>-1 and j>-1 and  i < ku and j<ch and not land[i][j] and [i,j] not in now:\n",
    "                now.append([i,j])\n",
    "                a.append([i,j])\n",
    "                for x in [-1,0,1]:\n",
    "                    for y in [-1,0,1]:\n",
    "                        check(i+x,j+y,now)\n",
    "        for i in range(ku):\n",
    "            for j in range(ch):\n",
    "                if land[i][j]==0 and [i,j] not in a:\n",
    "                    now = []\n",
    "                    check(i,j, now)\n",
    "                    print(now)\n",
    "                    if now:\n",
    "                        b.append(len(now))\n",
    "        print(b)\n",
    "        # b = [bb for bb in b if bb>0]\n",
    "        return sorted(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        n, m = len(land), len(land[0])\n",
    "        used = [[False]*m for _ in range(n)]\n",
    "        def dfs(x,y):\n",
    "            if not 0 <= x < n or not 0 <= y < m:return 0\n",
    "            if land[x][y] != 0:return 0\n",
    "            if used[x][y]:return 0\n",
    "            used[x][y] = True\n",
    "            cnt = 1\n",
    "            for i in range(x-1,x+2):\n",
    "                for j in range(y-1,y+2):\n",
    "                    cnt += dfs(i,j)\n",
    "            return cnt\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                temp = 0\n",
    "                if land[i][j] == 0 and not used[i][j]:\n",
    "                    temp = dfs(i,j)\n",
    "                    ans.append(temp)\n",
    "\n",
    "        ans.sort()\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m,n = len(land),len(land[0])\n",
    "        visited = [[False]*n for i in range(m)]\n",
    "        diff = [(0,1),(0,-1),(1,0),(-1,0),(-1,-1),(-1,1),(1,-1),(1,1)]\n",
    "        def dfs(i,j):\n",
    "            visited[i][j] =True\n",
    "            for x,y in diff:\n",
    "                ix,jy = i+x,j+y\n",
    "                if not(0<=ix<m and 0<=jy<n):continue\n",
    "                if not visited[ix][jy] and land[ix][jy]==0:\n",
    "                    dfs(ix,jy)\n",
    "                    ans[0]+=1\n",
    "                visited[ix][jy] = True\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not(not visited[i][j] and land[i][j]==0):continue\n",
    "                ans = [0]\n",
    "                dfs(i,j)\n",
    "                res.append(ans[0]+1)\n",
    "        return sorted(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        w_idx = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(x, y, area):\n",
    "            w_idx[x][y] = 1\n",
    "            for i in range(x-1, x+2):\n",
    "                for j in range(y-1, y+2):\n",
    "                    if 0 <= i < m and 0 <= j < n and land[i][j] == 0 and w_idx[i][j] == -1:\n",
    "                        area = dfs(i, j, area+1)\n",
    "            return area\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0 and w_idx[i][j] == -1:\n",
    "                    ans.append(dfs(i, j, 1))\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        viewed = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(x, y):\n",
    "            if x < 0 or y < 0 or x >= m or y >= n or land[x][y] != 0 or viewed[x][y] == 1:\n",
    "                return 0\n",
    "            res = 1\n",
    "            viewed[x][y] = 1\n",
    "            res += dfs(x-1, y-1)\n",
    "            res += dfs(x-1, y)\n",
    "            res += dfs(x-1, y+1)\n",
    "            res += dfs(x, y-1)\n",
    "            res += dfs(x, y+1)\n",
    "            res += dfs(x+1, y-1)\n",
    "            res += dfs(x+1, y)\n",
    "            res += dfs(x+1, y+1)\n",
    "            return res\n",
    "        res = []\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if land[x][y] == 0:\n",
    "                    resi = dfs(x,y)\n",
    "                    if resi:\n",
    "                        res.append(resi)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        \n",
    "        def union(x, y):\n",
    "            xx = find(x)\n",
    "            yy = find(y)\n",
    "            if xx != yy:\n",
    "                parent[xx] = yy\n",
    "                size[yy] += size[xx]\n",
    "        \n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        parent = {(i, j): (i, j) for i in range(m) for j in range(n) if land[i][j] == 0}\n",
    "        size = {(i, j): 1 for i in range(m) for j in range(n) if land[i][j] == 0}\n",
    "        ans = []\n",
    "        seen = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    for x, y in [[i-1, j], [i-1,j-1], [i,j-1], [i-1,j+1]]:\n",
    "                        if 0 <= x < m and 0 <= y < n and land[x][y] == 0:\n",
    "                            union((x, y), (i, j))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    p = find((i, j))\n",
    "                    if p not in seen:\n",
    "                        seen.add(p)\n",
    "                        ans.append(size[p])\n",
    "        ans.sort()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        row = len(land)\n",
    "        col = len(land[0])\n",
    "        pond_list = []\n",
    "        offset = [[-1, 0], [1,0],[0,-1],[0,1],[-1,-1],[1,1],[-1,1],[1,-1]]\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if i >= 0 and i < row and j >= 0 and j < col and land[i][j]==0:\n",
    "                land[i][j] = 1\n",
    "                d = 1\n",
    "                for off in offset:\n",
    "                    d += dfs(i+off[0],j+off[1])\n",
    "            else:\n",
    "                return 0\n",
    "            return d\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if land[i][j] == 0:\n",
    "                    pond_list.append(dfs(i,j))\n",
    "        pond_list.sort()\n",
    "        return (pond_list)\n",
    "    \n",
    "                            \n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.pa = [i for i in range(n)]\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x != self.pa[x]:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> int:\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.pa[root_x] = root_y\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    for ni, nj in [[i - 1, j], [i - 1, j - 1], [i - 1, j + 1], [i + 1, j], [i + 1, j - 1], [i + 1, j + 1], [i, j - 1], [i, j + 1]]:\n",
    "                        if 0 <= ni < m and 0 <= nj < n and land[ni][nj] == 0:\n",
    "                            uf.union(i * n + j, ni * n + nj)\n",
    "        \n",
    "        cnts = collections.defaultdict(lambda:0)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    p = uf.find(n * i + j)\n",
    "                    cnts[p] += 1\n",
    "        \n",
    "        if cnts:\n",
    "            return sorted([v for v in cnts.values()])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        visited = set()\n",
    "        def dfs(x, y):\n",
    "            if land[x][y] == 0 and (x, y) not in visited:\n",
    "                visited.add((x,y))\n",
    "                size = 1\n",
    "                for i, j in [(x-1,y), (x-1, y-1), (x-1,y+1), (x,y-1), (x,y+1), (x+1,y), (x+1,y-1), (x+1,y+1)]:\n",
    "                    if i >= 0 and i < m and j >=0 and j < n and land[i][j] == 0 and (i,j) not in visited:\n",
    "                        size += dfs(i, j)\n",
    "                return size\n",
    "            return 0\n",
    "        \n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                size = dfs(x, y)\n",
    "                if size > 0:\n",
    "                    ans.append(size)\n",
    "        ans.sort()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        ans = []\n",
    "\n",
    "        seen = set()\n",
    "        moves = ([-1, -1], [-1, 0], [-1, 1],\n",
    "                [0, -1], [0, 1],\n",
    "                [1, -1], [1, 0], [1, 1])\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            c = 1\n",
    "            seen.add((i, j))\n",
    "\n",
    "            for mx, my in moves:\n",
    "                i1, j1 = i+mx, j+my\n",
    "                if 0 <= i1 < m and 0 <= j1 < n and land[i1][j1] == 0 and (i1, j1) not in seen:\n",
    "                    c += dfs(i1, j1)\n",
    "                    \n",
    "            return c\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0 and (i, j) not in seen:\n",
    "                    ans.append(dfs(i, j))\n",
    "        \n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        visited = set()\n",
    "        m, n = len(land), len(land[0])\n",
    "        dx, dy = [0, 1, 1, 1, 0, -1, -1, -1], [1, 1, 0, -1, -1, -1, 0, 1]\n",
    "        ans = []\n",
    "        def dfs(x, y):\n",
    "            if land[x][y] != 0:\n",
    "                return 0\n",
    "            \n",
    "            t = 1\n",
    "            for i in range(8):\n",
    "                nx, ny = x + dx[i], y + dy[i]\n",
    "                if 0 <= nx < m and 0 <= ny < n and land[nx][ny] == 0 and (nx, ny) not in visited:\n",
    "                    visited.add((nx, ny))\n",
    "                    t += dfs(nx, ny)\n",
    "\n",
    "            return t\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0 and (i, j) not in visited:\n",
    "                    visited.add((i, j))\n",
    "                    ans.append(dfs(i, j))\n",
    "        ans.sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        size = []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        def DFS(i,j):\n",
    "            land[i][j] = 1\n",
    "            s = 1\n",
    "            for (dx, dy) in [(i+1, j), (i+1, j+1), (i+1, j-1), (i, j+1), (i, j-1), (i-1, j+1), (i-1, j-1), (i-1, j)]:\n",
    "                if dx >= 0 and dy >= 0 and dx < m and dy < n and land[dx][dy] == 0:\n",
    "                    s +=DFS(dx, dy)\n",
    "            return s\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    size.append(DFS(i,j))\n",
    "\n",
    "        return sorted(size)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        water=set()\n",
    "        res=[]\n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if land[i][j]==0:\n",
    "                    water.add((i,j))\n",
    "        visited=set()\n",
    "        def dfs(i,j):\n",
    "            if (i,j) not in water or (i,j) in visited:\n",
    "                return 0\n",
    "            visited.add((i,j))\n",
    "            return 1+dfs(i-1,j)+dfs(i+1,j)+dfs(i,j+1)+dfs(i,j-1)+dfs(i+1,j+1)+dfs(i-1,j-1)+dfs(i+1,j-1)+dfs(i-1,j+1)\n",
    "        for i in water:\n",
    "            if i not in visited:\n",
    "                res.append(dfs(i[0],i[1]))\n",
    "        res.sort()\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        ds = DisjoinSet(m*n+1)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    for (x,y) in [(-1,0),(1,0),(0,1),(0,-1),(-1,-1),(-1,1),(1,1),(1,-1)]:\n",
    "                        if i+x >=0 \\\n",
    "                        and i+x<m\\\n",
    "                        and j+y >=0 \\\n",
    "                        and j+y <n\\\n",
    "                        and land[i+x][j+y] == 0:\n",
    "                            ds.union(i*n+j,(i+x)*n+j+y)\n",
    "                            \n",
    "                else:\n",
    "                    ds.union(m*n,i*n+j)\n",
    "        ds.print()\n",
    "        return ds.count()\n",
    "\n",
    "class DisjoinSet:\n",
    "    def __init__(self,n):\n",
    "        self.parent = []\n",
    "        self.size = [1]*n\n",
    "        for i in range(n):\n",
    "            self.parent.append(i)\n",
    "\n",
    "    def find(self,x)->int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        return self.find(self.parent[x])\n",
    "\n",
    "    def union(self,x,y):\n",
    "        if self.find(x) != self.find(y):            \n",
    "            self.size[self.find(x)] +=self.size[self.find(y)]\n",
    "            self.size[self.find(y)] =0\n",
    "            self.parent[self.find(y)] = self.find(x)\n",
    "\n",
    "        \n",
    "\n",
    "    def count(self)->[]:\n",
    "        res = []\n",
    "        for i in range(len(self.size)-1):\n",
    "            if self.size[i] !=0:\n",
    "                res.append(self.size[i])\n",
    "        res.sort()\n",
    "        return res\n",
    "\n",
    "    def print(self):\n",
    "        print(self.parent)\n",
    "        print(self.size)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        ans = []\n",
    "\n",
    "        seen = set()\n",
    "        moves = ([-1, -1], [-1, 0], [-1, 1],\n",
    "                [0, -1], [0, 1],\n",
    "                [1, -1], [1, 0], [1, 1])\n",
    "        \n",
    "        def dfs(i, j, c):\n",
    "            c.append([i, j])\n",
    "            seen.add((i, j))\n",
    "            \n",
    "            for mx, my in moves:\n",
    "                i1, j1 = i+mx, j+my\n",
    "                if 0 <= i1 < m and 0 <= j1 < n and land[i1][j1] == 0 and (i1, j1) not in seen:\n",
    "                    dfs(i1, j1, c)\n",
    "            \n",
    "            if c not in ans:\n",
    "                ans.append(c)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0 and (i, j) not in seen:\n",
    "                    dfs(i, j, [])\n",
    "        \n",
    "        return sorted([len(i) for i in ans])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        ans = []\n",
    "\n",
    "        seen = set()\n",
    "        moves = ([-1, -1], [-1, 0], [-1, 1],\n",
    "                [0, -1], [0, 1],\n",
    "                [1, -1], [1, 0], [1, 1])\n",
    "        \n",
    "        def dfs(i, j, c):\n",
    "            c.append([i, j])\n",
    "            seen.add((i, j))\n",
    "            \n",
    "            for mx, my in moves:\n",
    "                i1, j1 = i+mx, j+my\n",
    "                if 0 <= i1 < m and 0 <= j1 < n and land[i1][j1] == 0 and (i1, j1) not in seen:\n",
    "                    dfs(i1, j1, c)\n",
    "            \n",
    "            if c not in ans:\n",
    "                ans.append(c)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0 and (i, j) not in seen:\n",
    "                    dfs(i, j, [])\n",
    "        \n",
    "        return sorted([len(i) for i in ans])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.size[fx] < self.size[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.size[fx] += self.size[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = i * n + j\n",
    "                if j < n - 1 and land[i][j] == 0 and land[i][j + 1] == 0:\n",
    "                    uf.union(index, index + 1)\n",
    "                if i < m - 1 and land[i][j] == 0 and land[i + 1][j] == 0:\n",
    "                    index_j = (i + 1) * n + j\n",
    "                    uf.union(index, index_j)\n",
    "                if j > 0 and i < m - 1 and land[i][j] == 0 and land[i + 1][j - 1] == 0:\n",
    "                    index_j = (i + 1) * n + j - 1\n",
    "                    uf.union(index, index_j)\n",
    "                if j < n - 1 and i < m - 1 and land[i][j] == 0 and land[i + 1][j + 1] == 0:\n",
    "                    index_j = (i + 1) * n + j + 1\n",
    "                    uf.union(index, index_j)\n",
    "        graph = collections.defaultdict(int)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    index = i * n + j\n",
    "                    graph[uf.find(index)] = uf.size[uf.find(index)]\n",
    "        ans = graph.values()\n",
    "        ans = sorted(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        n = len(land)\n",
    "        m = len(land[0])\n",
    "        uf = UnionFind(n*m)\n",
    "        res = []\n",
    "        dirs = [[0,1],[1,0],[-1,0],[0,-1],[-1,-1],[1,1],[1,-1],[-1,1]]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 0:\n",
    "                    for d in dirs:\n",
    "                        if d[0] + i < 0 or d[0] + i >= n or d[1] + j < 0 or d[1] + j >=m:\n",
    "                            continue\n",
    "                        if land[d[0] + i][d[1] + j] == 0:\n",
    "                            uf.union(i*m+j, (d[0]+i)*m+(d[1]+j)) \n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 0:\n",
    "                    p = uf.find(i*m+j)\n",
    "                    if p not in s:\n",
    "                        s.add(p)\n",
    "                        res.append(uf.size[p])\n",
    "        return sorted(res)\n",
    "\n",
    "        \n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        # self.roots = []\n",
    "\n",
    "    def find(self, p):\n",
    "        if self.parent[p] != p:\n",
    "            self.parent[p] = self.find(self.parent[p])\n",
    "        return self.parent[p]\n",
    "    \n",
    "    def union(self, p, q):\n",
    "        rootP = self.find(p)\n",
    "        rootQ = self.find(q)\n",
    "\n",
    "        if rootP != rootQ:\n",
    "            if self.size[rootP] > self.size[rootQ]:\n",
    "                self.parent[rootQ] = rootP\n",
    "                # self.roots.remove(rootQ)\n",
    "                self.size[rootP] += self.size[rootQ]\n",
    "\n",
    "            elif  self.size[rootP] <= self.size[rootQ]:\n",
    "                self.parent[rootP] = rootQ\n",
    "                # self.roots.remove(rootP)\n",
    "                self.size[rootQ] += self.size[rootP]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        D8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]\n",
    "        n, m = len(land), len(land[0])\n",
    "        dsu = DisjointSetUnion(n*m)\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                for dx, dy in D8:\n",
    "                    nx, ny = x+dx, y+dy\n",
    "                    if 0<=nx<n and 0<=ny<m and land[x][y] == land[nx][ny] == 0:\n",
    "                        dsu.union(x*m+y, nx*m+ny)\n",
    "        l = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if not land[i][j]:\n",
    "                    l.add(dsu.find(i*m+j))\n",
    "        return sorted([dsu.size[i] for i in l])\n",
    "\n",
    "class DisjointSetUnion:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.num_sets = n\n",
    " \n",
    "    def find(self, a):\n",
    "        acopy = a\n",
    "        while a != self.parent[a]:\n",
    "            a = self.parent[a]\n",
    "        while acopy != a:\n",
    "            self.parent[acopy], acopy = a, self.parent[acopy]\n",
    "        return a\n",
    " \n",
    "    def union(self, a, b):\n",
    "        a, b = self.find(a), self.find(b)\n",
    "        if a != b:\n",
    "            if self.size[a] < self.size[b]:\n",
    "                a, b = b, a\n",
    " \n",
    "            self.num_sets -= 1\n",
    "            self.parent[b] = a\n",
    "            self.size[a] += self.size[b]\n",
    " \n",
    "    def set_size(self, a):\n",
    "        return self.size[self.find(a)]\n",
    " \n",
    "    def __len__(self):\n",
    "        return self.num_sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        rows, cols = len(land), len(land[0])\n",
    "        n = rows * cols\n",
    "        dirs = (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)\n",
    "        roots = list(range(n + 1))\n",
    "        sz = [1] * (n + 1)\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                if sz[rx] > sz[ry]: rx, ry = ry, rx\n",
    "                sz[ry] += sz[rx]\n",
    "                roots[rx] = ry\n",
    "                # if sz[rx] < sz[ry]:\n",
    "                #     roots[rx] = ry\n",
    "                #     sz[ry] += sz[rx]\n",
    "                # else:\n",
    "                #     roots[ry] = rx\n",
    "                #     sz[rx] += sz[ry]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if land[r][c] == 0:\n",
    "                    for dr, dc in dirs:\n",
    "                        nr, nc = r + dr, c + dc\n",
    "                        if rows > nr >= 0 <= nc < cols:\n",
    "                            if land[nr][nc] == 0:\n",
    "                                union(r * cols + c, nr * cols + nc)\n",
    "                else:\n",
    "                    union(r * cols + c, n)\n",
    "        chils = defaultdict(int)\n",
    "        for x in range(n + 1):\n",
    "            if find(x) != find(n):\n",
    "                chils[find(x)] = sz[find(x)]\n",
    "        return sorted(chils.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        rows, cols = len(land), len(land[0])\n",
    "        n = rows * cols\n",
    "        dirs = (0, 1), (1, 0), (1, 1), (-1, 1), (1, -1)\n",
    "        roots = list(range(n + 1))\n",
    "        sz = [1] * (n + 1)\n",
    "        def find(x):\n",
    "            if roots[x] != x:\n",
    "                roots[x] = find(roots[x])\n",
    "            return roots[x]\n",
    "        def union(x, y):\n",
    "            rx, ry = find(x), find(y)\n",
    "            if rx != ry:\n",
    "                if sz[rx] > sz[ry]: rx, ry = ry, rx\n",
    "                sz[ry] += sz[rx]\n",
    "                roots[rx] = ry\n",
    "                # if sz[rx] < sz[ry]:\n",
    "                #     roots[rx] = ry\n",
    "                #     sz[ry] += sz[rx]\n",
    "                # else:\n",
    "                #     roots[ry] = rx\n",
    "                #     sz[rx] += sz[ry]\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if land[r][c] == 0:\n",
    "                    for dr, dc in dirs:\n",
    "                        nr, nc = r + dr, c + dc\n",
    "                        if rows > nr >= 0 <= nc < cols:\n",
    "                            if land[nr][nc] == 0:\n",
    "                                union(r * cols + c, nr * cols + nc)\n",
    "                else:\n",
    "                    union(r * cols + c, n)\n",
    "        chils = defaultdict(int)\n",
    "        for x in range(n + 1):\n",
    "            if find(x) != find(n):\n",
    "                chils[find(x)] = sz[find(x)]\n",
    "        return sorted(chils.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def find(self, arr, i, j, s):\n",
    "        if arr.shape[0] == 1:\n",
    "            m_range = []\n",
    "        elif i == 0:\n",
    "            m_range = [1]\n",
    "        elif i == arr.shape[0] -1:\n",
    "            m_range = [-1]\n",
    "        else:\n",
    "            m_range = [-1, 1]\n",
    "\n",
    "        if arr.shape[1] == 1:\n",
    "            n_range = []        \n",
    "        if j == 0:\n",
    "            n_range = [1]\n",
    "        elif j == arr.shape[1]-1:\n",
    "            n_range = [-1]\n",
    "        else:\n",
    "            n_range = [-1, 1]\n",
    "\n",
    "        if len(n_range) != 0:\n",
    "            for n in n_range:\n",
    "                if arr[i, j + n] == 0:\n",
    "                    s += 1\n",
    "                    \n",
    "                    arr[i, j + n] -= 1            \n",
    "                    s = self.find(arr, i, j + n, s)\n",
    "        if len(m_range) != 0:        \n",
    "            for m in m_range:\n",
    "                if arr[i + m, j] == 0:\n",
    "                    s += 1\n",
    "                    arr[i + m, j] -= 1\n",
    "                    s = self.find(arr, i + m, j, s)\n",
    "\n",
    "        if len(m_range) != 0 and len(n_range) != 0:                 \n",
    "            for m in m_range:\n",
    "                for n in n_range:\n",
    "                    if arr[i + m, j + n] == 0:\n",
    "                        s += 1\n",
    "                        arr[i + m, j + n] -= 1\n",
    "                        s = self.find(arr, i + m, j + n, s)\n",
    "        return s  \n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        land = np.array(land)\n",
    "        size = []\n",
    "        for i in range(land.shape[0]):\n",
    "            for j in range(land.shape[1]):\n",
    "                s = 0\n",
    "                if land[i,j] == 0:\n",
    "                    s += 1\n",
    "                    land[i, j] -= 1\n",
    "                    s = self.find(land, i, j, s)\n",
    "                    size.append(s)    \n",
    "        return sorted(size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        n = len(land)\n",
    "        m = len(land[0])\n",
    "        fa = [i for i in range(n * m)]\n",
    "        def find(i):\n",
    "            if i != fa[i]:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "        \n",
    "        def union(i, j):\n",
    "            # print(f\"union {i}, {j}, fa {find(i)}, fa {find(j)}\")\n",
    "            if i > j:\n",
    "                fa[find(i)] = find(fa[j])\n",
    "            else:\n",
    "                fa[find(j)] = find(fa[i])\n",
    "            # print(f\"union {i}, {j}, fa {find(i)}, fa {find(j)}\")\n",
    "            \n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] == 0:\n",
    "                    for x in range(-1, 2):\n",
    "                        for y in range(-1, 2):\n",
    "                            if x == y == 0:\n",
    "                                continue\n",
    "                            if 0 <= i + x < n and 0 <= j + y < m:\n",
    "                                if land[i + x][j + y] == 0:\n",
    "                                    union(i * m + j, (i + x) * m + j + y)\n",
    "                else:\n",
    "                    fa[i * m + j] = -1\n",
    "\n",
    "        \n",
    "        c = Counter()\n",
    "        for i in fa:\n",
    "            if i != -1:\n",
    "                c[find(i)] += 1\n",
    "        \n",
    "        ans = [item[1] for item in c.most_common()[::-1]]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.land = None\n",
    "        self.total_height = None\n",
    "        self.total_width = None\n",
    "        self.visited = None\n",
    "        self.cur_size = 0\n",
    "        self.result = list()\n",
    "\n",
    "    def init_param(self, land):\n",
    "        self.land = np.array(land)\n",
    "        self.total_height = self.land.shape[0]\n",
    "        self.total_width = self.land.shape[1]\n",
    "        self.visited = np.zeros_like(land)\n",
    "        self.cur_size = 0\n",
    "        self.result = list()\n",
    "\n",
    "    def get_next_positions(self, x, y):\n",
    "        next_list = list()\n",
    "        if 0 <= x <= self.total_height - 1 and 0 <= y <= self.total_width - 1:\n",
    "            for i in range(-1, 2):\n",
    "                for j in range(-1, 2):\n",
    "                    if 0 <= x + i <= self.total_height - 1 and 0 <= y + j <= self.total_width - 1:\n",
    "                        next_list.append((x + i, y + j))\n",
    "        return next_list\n",
    "\n",
    "    def dfs(self, x, y):\n",
    "        if self.visited[x][y] == 1:\n",
    "            return\n",
    "        if self.land[x][y] != 0:\n",
    "            return\n",
    "        self.cur_size += 1\n",
    "        self.visited[x][y] = 1\n",
    "        x_y_list = self.get_next_positions(x, y)\n",
    "        for new_x, new_y in x_y_list:\n",
    "            self.dfs(new_x, new_y)\n",
    "\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        self.init_param(land)\n",
    "        for x in range(self.total_height):\n",
    "            for y in range(self.total_width):\n",
    "                self.cur_size = 0\n",
    "                self.dfs(x, y)\n",
    "                if self.cur_size > 0:\n",
    "                    self.result.append(self.cur_size)\n",
    "        return sorted(self.result)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    land = [\n",
    "        [2, 8, 8, 4, 1, 7, 1, 5, 4, 2, 0, 8, 1, 9, 2, 5, 6, 9, 7, 4, 8, 9, 1, 7, 3, 6, 9, 3, 7, 1, 5, 7, 3, 1, 9, 9, 9,\n",
    "         6, 5, 1, 9, 9, 4, 1, 6, 4, 7, 6, 1, 6, 1, 3, 3, 9, 0, 3, 0, 0, 0, 1, 3, 1, 2, 0, 0, 0, 3, 2, 7, 3, 6, 7, 9],\n",
    "        [2, 0, 9, 8, 2, 0, 5, 8, 4, 0, 4, 5, 2, 1, 5, 6, 0, 6, 3, 3, 6, 9, 5, 4, 0, 9, 4, 7, 1, 4, 2, 8, 9, 8, 0, 6, 3,\n",
    "         5, 7, 2, 1, 6, 8, 4, 8, 4, 6, 5, 0, 3, 7, 1, 7, 6, 3, 0, 2, 2, 2, 3, 2, 4, 7, 7, 6, 8, 2, 9, 2, 5, 0, 3, 8],\n",
    "        [2, 7, 0, 1, 1, 3, 6, 5, 6, 0, 7, 0, 2, 4, 5, 0, 3, 7, 3, 1, 5, 7, 9, 8, 8, 0, 9, 8, 1, 9, 4, 7, 5, 6, 5, 4, 1,\n",
    "         7, 7, 4, 4, 3, 8, 3, 5, 3, 3, 8, 7, 4, 5, 4, 8, 0, 2, 0, 4, 7, 5, 4, 3, 9, 1, 9, 4, 9, 2, 2, 2, 4, 1, 2, 9],\n",
    "        [6, 0, 4, 4, 6, 7, 8, 8, 9, 9, 5, 4, 9, 7, 0, 4, 2, 7, 1, 9, 2, 2, 9, 2, 4, 3, 0, 5, 1, 7, 8, 9, 0, 5, 3, 3, 3,\n",
    "         1, 1, 7, 1, 2, 7, 5, 6, 8, 7, 2, 3, 1, 5, 3, 5, 7, 9, 7, 7, 8, 8, 7, 2, 4, 4, 2, 8, 2, 3, 2, 1, 9, 1, 2, 7],\n",
    "        [2, 5, 1, 2, 2, 5, 8, 2, 8, 7, 4, 5, 9, 8, 9, 6, 0, 9, 7, 0, 5, 8, 8, 3, 3, 8, 1, 9, 4, 8, 2, 3, 4, 9, 1, 2, 4,\n",
    "         5, 1, 5, 4, 4, 6, 9, 2, 3, 3, 1, 2, 2, 4, 1, 2, 7, 4, 6, 9, 2, 3, 5, 9, 7, 7, 4, 9, 9, 4, 7, 1, 5, 5, 7, 6],\n",
    "        [9, 9, 9, 1, 8, 3, 3, 4, 6, 5, 7, 7, 3, 1, 1, 3, 9, 2, 7, 0, 6, 8, 8, 0, 2, 9, 6, 6, 4, 4, 6, 2, 6, 6, 1, 7, 5,\n",
    "         6, 4, 9, 6, 9, 8, 2, 1, 4, 3, 4, 6, 6, 8, 6, 4, 7, 8, 3, 7, 1, 3, 7, 5, 3, 2, 1, 4, 7, 9, 7, 3, 4, 9, 0, 1],\n",
    "        [7, 1, 4, 9, 7, 2, 1, 9, 0, 9, 7, 4, 5, 3, 5, 2, 6, 5, 6, 0, 5, 0, 5, 3, 1, 1, 7, 9, 6, 2, 1, 8, 3, 4, 7, 4, 2,\n",
    "         1, 3, 5, 9, 7, 7, 5, 6, 1, 0, 3, 6, 3, 7, 9, 6, 5, 1, 4, 5, 7, 2, 3, 5, 3, 5, 2, 0, 9, 5, 1, 8, 6, 0, 0, 6],\n",
    "        [7, 9, 9, 8, 8, 3, 9, 7, 5, 1, 1, 8, 4, 4, 6, 3, 7, 2, 1, 9, 5, 6, 1, 2, 2, 5, 6, 3, 9, 6, 7, 9, 2, 7, 1, 4, 7,\n",
    "         3, 5, 0, 1, 2, 2, 5, 4, 9, 3, 1, 2, 1, 1, 0, 5, 1, 8, 4, 2, 1, 2, 4, 5, 4, 5, 6, 8, 7, 7, 4, 8, 3, 2, 7, 9],\n",
    "        [6, 6, 6, 7, 0, 8, 7, 6, 2, 6, 3, 1, 4, 6, 6, 9, 6, 2, 0, 5, 4, 9, 9, 9, 8, 8, 6, 2, 4, 3, 1, 6, 6, 4, 4, 4, 3,\n",
    "         1, 8, 1, 8, 3, 9, 5, 2, 7, 0, 0, 4, 0, 6, 9, 2, 0, 3, 1, 6, 3, 0, 7, 9, 3, 9, 4, 3, 6, 7, 9, 8, 9, 4, 2, 7],\n",
    "        [7, 8, 1, 8, 5, 3, 5, 1, 2, 9, 6, 2, 8, 7, 9, 7, 7, 8, 6, 3, 4, 4, 3, 2, 8, 6, 5, 7, 8, 5, 7, 5, 8, 3, 9, 6, 8,\n",
    "         9, 6, 6, 8, 7, 4, 9, 4, 6, 1, 1, 6, 7, 5, 6, 7, 0, 3, 3, 9, 3, 6, 1, 3, 8, 1, 2, 8, 3, 3, 6, 7, 9, 4, 4, 1],\n",
    "        [0, 7, 6, 7, 6, 4, 3, 1, 7, 8, 0, 0, 3, 1, 1, 7, 9, 2, 7, 9, 4, 9, 6, 2, 6, 6, 4, 0, 1, 8, 5, 6, 8, 1, 3, 8, 3,\n",
    "         7, 7, 9, 8, 4, 2, 8, 2, 5, 5, 9, 3, 3, 1, 6, 3, 1, 5, 2, 0, 4, 2, 2, 5, 4, 3, 4, 6, 7, 3, 4, 5, 1, 5, 7, 2],\n",
    "        [1, 7, 7, 6, 3, 4, 1, 8, 4, 3, 9, 8, 1, 5, 5, 4, 7, 7, 1, 8, 5, 7, 6, 4, 2, 6, 7, 7, 1, 3, 1, 7, 4, 8, 5, 2, 3,\n",
    "         9, 1, 2, 8, 2, 2, 0, 4, 5, 6, 1, 0, 4, 4, 2, 4, 9, 2, 4, 8, 2, 5, 5, 8, 2, 4, 8, 9, 3, 9, 1, 4, 5, 5, 5, 1],\n",
    "        [0, 1, 1, 8, 9, 1, 0, 1, 3, 0, 5, 9, 3, 4, 1, 7, 1, 2, 1, 7, 3, 4, 2, 7, 2, 9, 9, 7, 4, 8, 7, 4, 2, 6, 7, 8, 8,\n",
    "         4, 9, 6, 5, 9, 6, 3, 0, 0, 0, 6, 4, 0, 9, 8, 1, 7, 0, 9, 9, 3, 7, 5, 8, 9, 4, 9, 9, 1, 2, 7, 5, 3, 2, 2, 3],\n",
    "        [8, 8, 1, 9, 4, 8, 6, 7, 4, 8, 7, 7, 3, 1, 6, 2, 6, 3, 2, 8, 4, 9, 3, 5, 3, 7, 1, 1, 3, 7, 5, 6, 6, 1, 9, 3, 0,\n",
    "         6, 1, 7, 5, 1, 8, 1, 6, 7, 1, 8, 2, 2, 0, 5, 1, 0, 7, 6, 7, 9, 3, 2, 7, 8, 5, 5, 2, 1, 2, 3, 0, 1, 5, 0, 7],\n",
    "        [8, 1, 9, 4, 4, 5, 8, 3, 8, 5, 2, 3, 8, 4, 5, 6, 5, 0, 4, 0, 6, 7, 5, 5, 2, 7, 8, 5, 2, 1, 4, 9, 5, 1, 3, 4, 8,\n",
    "         7, 7, 3, 8, 5, 1, 5, 5, 9, 3, 9, 0, 0, 0, 8, 0, 4, 0, 5, 3, 8, 5, 1, 5, 0, 1, 7, 1, 3, 7, 4, 2, 9, 5, 5, 4],\n",
    "        [5, 3, 5, 5, 4, 4, 1, 5, 6, 1, 7, 4, 0, 7, 5, 8, 0, 3, 6, 7, 0, 4, 4, 8, 3, 2, 6, 3, 8, 0, 9, 8, 9, 9, 3, 2, 7,\n",
    "         6, 9, 6, 3, 1, 8, 8, 6, 4, 9, 4, 4, 2, 7, 5, 0, 1, 5, 0, 8, 9, 4, 1, 6, 9, 8, 7, 0, 1, 7, 3, 4, 6, 1, 1, 8],\n",
    "        [1, 9, 5, 4, 1, 7, 0, 6, 3, 2, 1, 5, 3, 1, 8, 7, 5, 7, 6, 6, 8, 0, 3, 8, 8, 2, 5, 6, 7, 2, 7, 8, 2, 1, 5, 3, 9,\n",
    "         3, 5, 2, 2, 9, 4, 7, 8, 6, 7, 7, 9, 8, 6, 3, 0, 6, 9, 7, 3, 1, 9, 1, 9, 1, 5, 6, 3, 7, 1, 0, 8, 9, 9, 8, 1],\n",
    "        [5, 8, 5, 7, 7, 8, 0, 7, 9, 2, 0, 4, 5, 8, 8, 7, 8, 6, 5, 4, 6, 3, 4, 1, 7, 2, 8, 7, 4, 7, 5, 2, 5, 5, 9, 3, 3,\n",
    "         7, 1, 6, 5, 1, 9, 5, 5, 5, 6, 2, 1, 3, 6, 8, 1, 0, 5, 2, 8, 8, 9, 9, 3, 0, 5, 3, 3, 8, 1, 4, 5, 8, 3, 2, 7]]\n",
    "    s = Solution()\n",
    "    res = s.pondSizes(land)\n",
    "    print(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        dirs = [[0,1],[1,0],[0,-1],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        fa = [i for i in range(len(land)*len(land[0]))]\n",
    "        cnts = [1 for i in range(len(land)*len(land[0]))] \n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                if land[i][j]==0:\n",
    "                     for dirr in dirs:\n",
    "                        nexti = dirr[0]+i\n",
    "                        nextj = dirr[1]+j\n",
    "                        if (nexti<0 or nextj<0 or nexti>=len(land) or nextj>=len(land[0]) or land[nexti][nextj] != 0):\n",
    "                            continue\n",
    "                        else:\n",
    "                            nowId = self.getId(i, j, len(land[0]))\n",
    "                            nextId = self.getId(nexti, nextj, len(land[0]))\n",
    "                            if self.find(nowId, fa)!=self.find(nextId, fa):\n",
    "                                self.union(nowId, nextId, cnts, fa)\n",
    "        res = []                  \n",
    "        for i in range(len(land)):\n",
    "            for j in range(len(land[0])):\n",
    "                nowId = self.getId(i, j, len(land[0]))\n",
    "                if (fa[nowId]==nowId and land[i][j] ==0):\n",
    "                    res.append(cnts[nowId])\n",
    "        \n",
    "        res.sort(reverse=False)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "    def find(self,x,fa):\n",
    "        if x==fa[x]:\n",
    "            return x\n",
    "        fa[x] = self.find(fa[x], fa)\n",
    "        return fa[x]\n",
    "    \n",
    "    \n",
    "\n",
    "    def union(self,x,y,cnts,fa):\n",
    "        root_x = self.find(x, fa)\n",
    "        root_y = self.find(y, fa)\n",
    "        fa[root_x] = self.find(root_y,fa)\n",
    "        cnts[root_y] += cnts[root_x]\n",
    "    \n",
    "    def getId(self,x,y,col):\n",
    "        return x*col+y\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m,n = len(land),len(land[0])\n",
    "        fa = [i for i in range(m*n)]\n",
    "        cnt = [1]*(m*n)\n",
    "        direc = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x,y):\n",
    "            i,j = find(x),find(y)\n",
    "            fa[find(x)] = find(y)\n",
    "            cnt[j] += cnt[i]\n",
    "        def dfs(i,j):\n",
    "            land[i][j] = -1\n",
    "            for dire in direc:\n",
    "                x = i+dire[0]\n",
    "                y = j+dire[1]\n",
    "                if x <0 or y <0 or x >m-1 or y > n-1 or land[x][y] != 0:\n",
    "                    continue\n",
    "                union(i*n+j,x*n+y)\n",
    "                land[x][y] = -1\n",
    "                dfs(x,y)\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    dfs(i,j)\n",
    "                    \n",
    "        # print(fa,land)\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if fa[i*n+j] == i*n+j and land[i][j] == -1:\n",
    "                    res.append(cnt[i*n+j])\n",
    "        res.sort()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        def dfs(x, y):\n",
    "            nonlocal m, n\n",
    "            land[x][y] = -1\n",
    "            tmp = 0\n",
    "            for dx, dy in [(1,0),(-1,0),(0,1),(0,-1),(-1,-1),(-1,1),(1,-1),(1,1)]:\n",
    "                nx = x+dx\n",
    "                ny = y+dy\n",
    "                if 0<=nx<m and 0<=ny<n and land[nx][ny] == 0:\n",
    "                    tmp += dfs(nx, ny)\n",
    "            return 1+tmp\n",
    "\n",
    "        m, n = len(land), len(land[0])\n",
    "        cnt = [0] * 1000001\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    cnt[dfs(i, j)] += 1\n",
    "        ans = []\n",
    "        for i in range(1000001):\n",
    "            if cnt[i]:\n",
    "                for j in range(cnt[i]): \n",
    "                    ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m, n = len(land), len(land[0])\n",
    "        \n",
    "        def union(x, y):\n",
    "            xx = find(x)\n",
    "            yy = find(y)\n",
    "            if xx == yy:\n",
    "                return\n",
    "            if size[xx] > size[yy]:\n",
    "                xx, yy = yy, xx\n",
    "            parent[xx] = yy\n",
    "            size[yy] += size[xx]\n",
    "            if rank[xx] == rank[yy]:\n",
    "                rank[yy] += 1\n",
    "        \n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        parent = {(i, j): (i, j) for i in range(m) for j in range(n) if land[i][j] == 0}\n",
    "        size = {(i, j): 1 for i in range(m) for j in range(n) if land[i][j] == 0}\n",
    "        rank = {(i, j): 1 for i in range(m) for j in range(n) if land[i][j] == 0}\n",
    "        ans = []\n",
    "        seen = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] != 0:\n",
    "                    continue\n",
    "                for x, y in [[i-1, j], [i-1,j-1], [i,j-1], [i-1,j+1]]:\n",
    "                    if 0 <= x < m and 0 <= y < n and land[x][y] == 0:\n",
    "                        union((x, y), (i, j))\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] != 0:\n",
    "                    continue\n",
    "                p = find((i, j))\n",
    "                if p in seen:\n",
    "                    continue\n",
    "                seen.add(p)\n",
    "                ans.append(size[p])\n",
    "        ans.sort()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        dx = [1,1,0,-1,-1,-1,0,1]\n",
    "        dy = [0,1,1,1,0,-1,-1,-1]\n",
    "        num = []\n",
    "        m = len(land)\n",
    "        n = len(land[0])\n",
    "        col = np.zeros((m,n))\n",
    "        #print(col)\n",
    "        def dfs(i,j,cnt):\n",
    "            if i >= m or i < 0 or j >= n or j < 0:\n",
    "                return\n",
    "            if land[i][j] > 0 or col[i][j] > 0:\n",
    "                return\n",
    "            else:\n",
    "                col[i][j] = cnt\n",
    "                num[cnt] += 1\n",
    "                for dir in range(8):\n",
    "                    dfs(i+dx[dir],j+dy[dir],cnt)\n",
    "        cnt = 1\n",
    "        num.append(0)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if col[i][j] == 0 and land[i][j] == 0:    \n",
    "                    num.append(0)\n",
    "                    dfs(i,j,cnt)\n",
    "                    cnt = cnt + 1\n",
    "        del(num[0])\n",
    "        num = sorted(num)\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        n = len(land)\n",
    "        m = len(land[0])\n",
    "        visied = set()\n",
    "\n",
    "        def gfs(ii, jj):\n",
    "            if land[ii][jj]:\n",
    "                return 0\n",
    "            if (ii,jj) in visied:\n",
    "                return 0\n",
    "            result = 0\n",
    "            stack = [(ii,jj)]\n",
    "            visied.add((ii,jj))\n",
    "            while len(stack):\n",
    "                i,j=stack.pop(0)\n",
    "                if land[i][j]:\n",
    "                    continue\n",
    "                result+=1\n",
    "                for x,y in [(i-1, j),(i,j-1),(i+1,j),(i,j+1),(i-1,j-1),(i+1,j+1),(i-1,j+1), (i+1, j-1)]:\n",
    "                    if  (x,y) in visied or x<0 or y<0 or x>=n or y>=m:\n",
    "                        continue\n",
    "                    stack.append((x,y))\n",
    "                    visied.add((x,y))\n",
    "            return result\n",
    "        results=[]\n",
    "        for k in range(n):\n",
    "            for f in range(m):\n",
    "                re = gfs(k,f)\n",
    "                if re>0:\n",
    "                    results.append(re)\n",
    "        results = sorted(results)           \n",
    "        return results\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        g = []\n",
    "        m, n = len(land), len(land[0])\n",
    "        ret = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                g.append([])\n",
    "                if land[i][j] == 0:\n",
    "                    if j+1 < n and land[i][j+1] == 0:\n",
    "                        g[-1].append((i, j+1))\n",
    "                    if i+1 < m and j+1 < n and land[i+1][j+1] == 0:\n",
    "                        g[-1].append((i+1, j+1))\n",
    "                    if i+1 < m and land[i+1][j] == 0:\n",
    "                        g[-1].append((i+1, j))\n",
    "                    if i+1 < m and j-1 >= 0 and land[i+1][j-1] == 0:\n",
    "                        g[-1].append((i+1, j-1))\n",
    "                    if j-1 >= 0 and land[i][j-1] == 0:\n",
    "                        g[-1].append((i, j-1))\n",
    "                    if i-1 >=0 and j-1 >=0 and land[i-1][j-1] == 0:\n",
    "                        g[-1].append((i-1,j-1))\n",
    "                    if i-1 >= 0 and land[i-1][j] == 0:\n",
    "                        g[-1].append((i-1, j))\n",
    "                    if i-1 >= 0 and j+1 < n and land[i-1][j+1] == 0:\n",
    "                        g[-1].append((i-1, j+1))\n",
    "        visited = [[0] * n for i in range(m)]\n",
    "        que = Queue()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0 and land[i][j] == 0:\n",
    "                    que.put((i, j))\n",
    "                    self.bfs(land, g, visited, que, ret)\n",
    "        ret.sort()\n",
    "        return ret\n",
    "    def bfs(self, land, g, visit, stack, ret):\n",
    "        temp = 0\n",
    "        m, n = len(land), len(land[0])\n",
    "        while stack.qsize() != 0:\n",
    "            idx = stack.get()\n",
    "            if visit[idx[0]][idx[1]] == 1:\n",
    "                continue\n",
    "            temp += 1\n",
    "            visit[idx[0]][idx[1]] = 1\n",
    "            for i in g[n*idx[0] + idx[1]]:\n",
    "                stack.put(i)\n",
    "        ret.append(temp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        if len(land) == 0: return []\n",
    "        m, n = len(land), len(land[0])\n",
    "        p, sizes = [0] * (m * n), [0] * (m * n)\n",
    "\n",
    "        def find(x):\n",
    "            return x if x == p[x] else find(p[x])\n",
    "        def connect(x, y):\n",
    "            rootX, rootY = find(x), find(y)\n",
    "            if rootX != rootY:\n",
    "                p[rootX] = rootY\n",
    "                sizes[rootY] += sizes[rootX]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = i * n + j\n",
    "                p[x] = x\n",
    "                if land[i][j] == 0:\n",
    "                    sizes[x] = 1\n",
    "                    if j > 0 and land[i][j - 1] == 0: connect(x, x - 1)\n",
    "                    if i > 0:\n",
    "                        if j > 0 and land[i - 1][j - 1] == 0: connect(x, x - n - 1)   \n",
    "                        if land[i - 1][j] == 0: connect(x, x - n)\n",
    "                        if j < n - 1 and land[i - 1][j + 1] == 0: connect(x, x - n + 1)\n",
    "                # print (f'after [{i}][{j}]: \\n{p}\\n{sizes}')\n",
    "\n",
    "\n",
    "        \n",
    "        ret = []\n",
    "        for i in range(m * n):\n",
    "            if p[i] == i and sizes[i] > 0:\n",
    "                ret.append(sizes[i])\n",
    "\n",
    "        return sorted(ret)\n",
    "                    \n",
    "                    \n",
    "        \n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        m,n = len(land),len(land[0])\n",
    "        fa = [i for i in range(m*n)]\n",
    "        cnt = [1]*(m*n)\n",
    "        direc = [[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(x,y):\n",
    "            i,j = find(x),find(y)\n",
    "            fa[find(x)] = find(y)\n",
    "            cnt[j] += cnt[i]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    # land[i][j] = -1\n",
    "                    for dire in direc:\n",
    "                        x = i+dire[0]\n",
    "                        y = j+dire[1]\n",
    "                        if x <0 or y <0 or x >m-1 or y > n-1 or land[x][y] != 0:\n",
    "                            continue\n",
    "                        if find(i*n+j) != find(x*n+y):\n",
    "                            union(i*n+j,x*n+y)                    \n",
    "        # print(fa,land)\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if fa[i*n+j] == i*n+j and land[i][j] == 0:\n",
    "                    res.append(cnt[i*n+j])\n",
    "        res.sort()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        n, m = len(land), len(land[0])\n",
    "        pre = [_ for _ in range(n * m)]\n",
    "        zero = []\n",
    "\n",
    "        def find(x):\n",
    "            # 传入的得是index\n",
    "            if pre[x] == x:\n",
    "                return x\n",
    "            res = find(pre[x])\n",
    "            pre[x] = res\n",
    "            return res\n",
    "\n",
    "        def union(x, y):\n",
    "            res_x, res_y = find(x), find(y)\n",
    "            if res_x == res_y:\n",
    "                return\n",
    "            pre[res_x] = res_y\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if land[i][j] != 0:\n",
    "                    continue\n",
    "                index = i * m + j\n",
    "                zero.append(index)\n",
    "                directions = [(-1, 0), (-1, -1), (0, -1), (1, -1)]  # 左 | 左上 | 上\n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if 0 <= x < n and 0 <= y < m and land[x][y] == 0:\n",
    "                        union(index, x * m + y)\n",
    "\n",
    "        cnt = Counter()\n",
    "        for water in zero:\n",
    "            parent = find(water)\n",
    "            cnt[parent] += 1\n",
    "        return sorted(list(cnt.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "        result = []\n",
    "        l = len(land)\n",
    "        n = len(land[0])\n",
    "        import numpy as np\n",
    "        #matrix = np.zeros((l,n), dtype=int)\n",
    "\n",
    "        def dfs(x, y):\n",
    "            if not (x >= 0 and y >=0 and x < l and y < n  and land[x][y] ==0):\n",
    "                return 0\n",
    "            land[x][y] = -1\n",
    "            res = 1\n",
    "            for t, w in [[-1,0],[1,0],[-1,-1],[-1,1],[1,-1],[1,1],[0,1],[0,-1]]:\n",
    "                tmp_x = x + t\n",
    "                tmp_y = y + w\n",
    "                #if matrix[tmp_x][tmp_y] == 0:\n",
    "                res += dfs(tmp_x,tmp_y)\n",
    "            return res\n",
    "\n",
    "        for i in range(l):\n",
    "            for j in range(n):\n",
    "                if land[i][j] == 0:\n",
    "                    ret = dfs(i,j)\n",
    "                    if ret >0:\n",
    "                        result.append(ret)\n",
    "        result.sort()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def pondSizes(self, land: List[List[int]]) -> List[int]:\n",
    "    m, n = len(land), len(land[0])\n",
    "    parent, size = [_ for _ in range(m * n)], [1 for _ in range(m * n)]\n",
    "\n",
    "    def find(node):\n",
    "      if parent[node] == node: return node\n",
    "      else:\n",
    "        parent[node] = find(parent[node])\n",
    "        return parent[node]\n",
    "    \n",
    "    def union(i, j):\n",
    "      parent_i, parent_j = find(i), find(j)\n",
    "      parent[parent_i] = find(parent_j)\n",
    "      size[parent_j] += size[parent_i]\n",
    "    \n",
    "    dirs = [[0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [-1, 1], [1, -1], [-1, -1]]\n",
    "\n",
    "    res = []\n",
    "    \n",
    "    for i in range(m):\n",
    "      for j in range(n):\n",
    "        if land[i][j] == 0:\n",
    "          for dir in dirs:\n",
    "            ni, nj = i + dir[0], j + dir[1]\n",
    "            if ni >= 0 and nj >= 0 and ni < m and nj < n and land[ni][nj] == 0:\n",
    "              id1, id2 = i * n + j, ni * n + nj\n",
    "              if find(id1) != find(id2): union(id1, id2)\n",
    "    \n",
    "    for i in range(m):\n",
    "      for j in range(n):\n",
    "        id = i * n + j\n",
    "        if parent[id] == id and land[i][j] == 0:\n",
    "          res.append(size[id])\n",
    "    \n",
    "    return sorted(res)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
